package practise.alogrithm.introductionToAlogrithm.foundations;

import javax.sound.midi.SysexMessage;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * a complete merge sorting
 */
public class MergeSorting {
    public static List<Integer> mergeSorting(List<Integer> arrays){
        if(arrays.size()<2){
            return arrays;
        }
        List<Integer> left = mergeSorting(new ArrayList<>(arrays.subList(0,(arrays.size()/2))));
        List<Integer> right = mergeSorting(new ArrayList<>(arrays.subList((arrays.size() / 2), arrays.size())));
        int size = arrays.size();
        arrays.clear();
        for(int i =0 ; i<size;i++){
            // there, we'd better use a queue instead of the list, as if we use the list, we have to always check the index bound
            if(left.size()!=0 && right.size()!=0){
                if(left.get(0)<right.get(0))
                    arrays.add(left.remove(0));
                else
                    arrays.add(right.remove(0));

            }
            else{
                if(left.size()==0)
                    arrays.add(right.remove(0));
                else
                    arrays.add(left.remove(0));
            }
        }
        return arrays;
    }

    public static void main(String[] args){
        List<Integer> array = new ArrayList<>(Arrays.asList(new Integer[]{1,3,2,5,4,6,7,8,0,9,}));
        for(Integer value: mergeSorting(array))
        System.out.print("["+value+"]");
    }
}
